/*
Date:20210430 23:52PM
key:其中一个遍历到尾巴，然后头尾相连。变成炸弹的样子，然后直接调用
    142. 环形链表 II 的函数即可。

    官方解法：
    方法3初看很难理解，但是细想就会发现很简单很巧妙 A和B两个链表长度可能不同，但是A+B和B+A的长度是相同的，所以遍历A+B和遍历B+A一定是同时结束。 如果A,B相交的话A和B有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点 如果A,B不相交的话两个指针就会同时到达A+B（B+A）的尾节点(即NULL)

    关键思想在于走相同的路程。然后结尾一定是二者相等，无论是走到交点还是没有交点同为null
 */
class Solution {
public:
ListNode *detectCycle(ListNode *head)
    {
        if(head==NULL){return NULL;}
        if(head->next==head){return head;}
        ListNode* quick=head;
        ListNode* slow=head;
        int i=2;
        bool cyc=0;
        while(quick!=NULL)
        {
            if(i%2){slow=slow->next;}
            quick=quick->next;
            if(quick==slow){cyc=1;break;}
            i++;
        }   
        //cout<<cyc;
        if(cyc)
        {
            //如果cyc=1，上面的quick最后一定在这个循环链表里。
            //这时从head开始，一步一步往前走
            ListNode* p=head;

            while(1)
            {
                //在已知循环内转一圈.
                ListNode* p1=quick;
                
                for(int i=0;;i++)
                {
                    if(i!=0)
                    {
                        if(p1==quick){break;}
                    }
                    if(p1==p){return p;}
                        p1=p1->next;
            
                }
                //没找到就是p还没进到环
                p=p->next;
            }

        }
        else
        {
            return NULL;
        }


    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode *p=headA;
        ListNode *p1=headB;

        while(p!=p1)
        {
            if(p!=NULL)
            {
                p=p->next;
            }
            else{p=headB;}
            if(p1!=NULL)
            {
                p1=p1->next;
            }
            else{p1=headA;}

        }

        return p;
    }
};